package LC;

import java.util.Arrays;

/**
 * https://leetcode.com/problems/maximum-subarray/description/
 * Find the contiguous subarray within an array (containing at least one number) which has the largest sum.
 * For example, given the array [-2,1,-3,4,-1,2,1,-5,4],
 * the contiguous subarray [4,-1,2,1] has the largest sum = 6.
 */
public class LC_053_MaximumSubarray_DP_Greedy {
    public static void main(String[] args) {
        int[] a = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
        int n = Solution.maxSubArray(a);
        System.out.println(n);
    }

    static class Solution {
        static int maxSubArray(int[] nums) {
            int[] sum = new int[nums.length];
            int max = nums[0];
            sum[0] = nums[0];

            for (int i = 1; i < nums.length; i++) {
                sum[i] = Math.max(nums[i], sum[i - 1] + nums[i]);
                max = Math.max(max, sum[i]);
            }

            System.out.println(Arrays.toString(sum));
            return max;
        }
    }
}
